package com.leecode.xiehf.page_02;

import com.leecode.Printer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
 * <p>
 * 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
 * <p>
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * 给定 n 和 k，返回第 k 个排列。
 * <p>
 *  
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/permutation-sequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0060 extends Printer {

    public static void main(String[] args) {
        Solution_0060 solution = new Solution_0060();
        String s = solution.getPermutation(4, 9);
        print(s);
    }



    public String getPermutation(int n, int k) {
        // 每次将k对n-1的阶乘 取除的结果 就是第一位的数字
        StringBuilder stringBuilder = new StringBuilder();
        int[] factories = new int[n + 1];
        List<Integer> list = new ArrayList<>();
        factories[0] = 1;
        int fact =1 ;
        for (int i = 1; i <= n; i++) {
            fact *= i;
            factories[i] = fact;
            list.add(i);
        }
        // 从0计数
        if (k > factories[n]) {
            return null;
        }
        k -= 1;
        for (int i = n - 1; i >= 0; i--) {
            int index = k / factories[i];
            stringBuilder.append(list.remove(index));
            k-= index * factories[i];
        }
        return stringBuilder.toString();
    }

}
